/***
 * 基于数组实现最大堆
 */
public class MaxHeap<E extends  Comparable<E>> {
    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }
    public MaxHeap(){
        data =new Array<>();
    }

    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for(int i=parent(arr.length-1);i>=0;i--){
            siftDown(i);
        }
    }

    public int getSize(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    /***
     * 返回一个完全二叉树表示中,index号元素索引对应的父节点的索引
     * @param index
     * @return
     */
    public int parent(int index){
        if(index == 0){
            throw new IllegalArgumentException("index : 0 doesn`t have parent");
        }
        return (index-1 )/2;
    }

    /***
     * 返回一个完全二叉树表示中,index索引对应的左孩子的索引
     * @param index
     * @return
     */
    public int leftChild(int index){
        return index *2 + 1;
    }

    /***
     * 返回一个完全二叉树表示中,index索引对应的右孩子的索引
     * @param index
     * @return
     */
    public int rightChild(int index){
        return index *2 + 2;
    }

    /***
     * 向堆中添加元素
     * @param e
     */
    public void add(E e){
        data.addLast(e);
        //维护堆的性质
        suftUp(data.getSize() - 1);
    }

    private void suftUp(int k) {
       while (k>0 && data.get(k).compareTo(data.get(parent(k))) > 0){
           //交换元素
           data.swap(k,parent(k));
           k = parent(k);
       }
    }

    //查找最大堆的最大值
    public E findMax(){
        if(data.isEmpty()){
            throw new IllegalArgumentException("can not do this operation with empty heap");
        }
        return data.get(0);
    }

    //从堆中抽出最大值
    public E extractMax(){
        E max = findMax();
        data.swap(0,data.getSize()-1);
        data.removeLast();
        //下沉操作维护堆性质
        siftDown(0);
        return max;
    }

    private void siftDown(int k) {
        while(leftChild(k) < data.getSize()){
            int j = leftChild(k);
            if(j+1 < data.getSize() && data.get(j+1).compareTo(data.get(j)) > 0){
                j = rightChild(k);
                //j等于左右孩子中最大的那个
            }
            if(data.get(j).compareTo(data.get(k)) > 0){
                break;
            }
            data.swap(j,k);
            k = j;
        }
    }

    //取出堆中最大元素,并替换成元素e
    public E replace(E e){
        E max = findMax();
        data.set(0,e);
        //维护堆的性质
        siftDown(0);
        return max;
    }

}
